COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	prolog[w84,jmc]		Higher level logic programming than prolog allows
C00007 ENDMK
C⊗;
prolog[w84,jmc]		Higher level logic programming than prolog allows

Notes

1. The natural language for programming may be naive set theory -
or an extension thereof.  We say "naive", because it may be a language
requiring circumscription to circumscribe it and make it into
a formalized language.  Sorry this is still vague.

2. The map coloring and eight queens problems may provide good examples.

3. The Pereira-Porto program is not a general map coloring program; it
is a program for coloring a particular map.  It is rare for these
alternatives to be so blatantly available, because the best way
to solve a particular problem often involves writing a general
program and applying it to the problem.  Chris Goad makes the
distinction.

4. There may be no higher directly executable logic programming
language than Prolog.  The higher level languages may require
compiling (or even thinking).  The particular assertions of a
logical description of a problem and its solution method affect
non-monotonically (in a very generalized sense) the computations
that are performed.  Prolog is a discovery that more can be done
with a directly executable system than had been previously thought.

5. Some program fragments.

iscolor(Red) ∧ ...

Perhaps even  circumcscribe(iscolor)?

Otherwise  colors = {Red, Green, Yellow, Blue}.

We need both abstract objects, e.g. maps, and representations of them
in our description of the program.  The representations may themselves
be described rather abstractly.

(declare countries |finset|); hinting at EKL which may have some more
direct use.  We might indeed compile out of EKL.

maps = {z ⊂ countries ⊗ countries | (∀x.¬z(x,x)) ∧ [∀x y.z(x,y) ≡ z(y,x)]}

This assumes  countries  to be predefined.  Therefore, it may be better to
use the customary mathematical process of writing something like

maps = {(countries,z) | countries ε finsets ∧ z ⊂ countries ⊗ countries ∧
		(∀x.¬z(x,x)) ∧ [∀x y.z(x,y) ≡ z(y,x)]}

colorings(z) = {f ε countries→colors | ∀x y.z(x,y) ⊃ x ≠ y}

6. Now we need some representations.  First we need to represent maps by
lists of lists, where for each country we have a sublist starting with
it and followed by the list of countries adjacent to it.  Maybe this
is already too concrete, because we might want to avoid list operations
in favor of some kind of hashing, and we may want to describe an
algorithm before deciding whether to use lists.
Perhaps we can stay with the set theoretic concepts a while longer.

7. Our goal is to decide how to express logic and control.  In particular
we want to express the postponement and Kempe heuristics.

8. Taking the problem from the other end, we could look for a minimal
improvement on Prolog.